package com.future;

import java.util.*;

/**
 * Description:
 * ����һ�����������ź���ĸ��ɵ��ַ��� s ��ɾ����С��������Ч���ţ�ʹ��������ַ�����Ч��
 * <p>
 * �������п��ܵĽ�����𰸿��԰� ����˳�� ���ء�
 * <p>
 * ?
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺s = "()())()"
 * �����["(())()","()()()"]
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/remove-invalid-parentheses
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/3/30 14:27
 */
public class Solution_301 {

    public static void main(String[] args) {
        String s = "()())";
        //s = "(a)())()";
        List<String> list = removeInvalidParentheses(s);
        System.out.println(list);
    }


    public static List<String> removeInvalidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return new ArrayList<>();
        }
        List<String> ans = new ArrayList<>();
        process(s, 0, 0, ans, new char[]{'(', ')'});
        return ans;
    }

    private static void process(String s, int checkIndex, int deleteIndex, List<String> ans, char[] symbols) {
        int count = 0;
        for (int i = checkIndex; i < s.length(); i++) {
            if (s.charAt(i) == symbols[0]) {
                count++;
            } else if (s.charAt(i) == symbols[1]) {
                count--;
            }
            if (count < 0) {
                for (int j = deleteIndex; j <= i; j++) {
                    if (s.charAt(j) == symbols[1]
                            && (j == deleteIndex || s.charAt(j - 1) != symbols[1])) {// �ص㣬ȥ��
                        process(s.substring(0, j) + s.substring(j + 1), i, j, ans, symbols);
                    }
                }
                return; // �ص㣬ֱ�ӷ���
            }
        }
        String reverseStr = new StringBuilder(s).reverse().toString();
        if (symbols[0] == '(') {
            process(reverseStr, 0, 0, ans, new char[]{')', '('});
        } else {
            ans.add(reverseStr);
        }

    }
}
